package summer.presum;

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class Solution497 {
    int[][] rs;
    int[] sum;
    int n;

    Random random = new Random();

    public Solution497(int[][] rects) {
        rs = rects;
        n = rects.length;
        sum = new int[n];
        int pre = 0;
        for (int i = 0; i < n; i++) {
            int cur = (rects[i][2] - rects[i][0] + 1) * (rects[i][3] - rects[i][1] + 1);
            sum[i] = pre + cur;
            pre = sum[i];
        }
    }

    public int[] pick() {
        int num = random.nextInt(sum[n - 1]) + 1;
        int i = 0;
        int j = n - 1;
        while (i < j) {
            int mid = (i + j) >> 1;
            if (sum[mid] >= num) j = mid;
            else i = mid + 1;
        }
        int[] nums = rs[i];
        int x = random.nextInt(nums[2] - nums[0] + 1) + nums[0];
        int y = random.nextInt(nums[3] - nums[1] + 1) + nums[1];
        return new int[]{x, y};
    }
}
